﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Ecosystème
{
    public class Dijkstra
    {
        public List<Vertex> les_stations;
        public Dijkstra(List<Vertex> stations)
        {
            les_stations = stations;
        }

        //ouverture du Sommet de cout minimum parmis les Sommets non visites
        public Vertex ouvre_min(List<Vertex> liste)
        {
            Vertex res = new Vertex(0, 0, "nulle part");
            res.set_cout(double.MaxValue);
            foreach (Vertex s in liste)
            {
                if (s.cout() <= res.cout())
                    res = s;

            }
            liste.Remove(res);
            return res;
        }
        //l'algo de Dijkstra proprement dit
        public List<Vertex> trouver_chemin(Vertex depart, Vertex destination)
        {

            List<Vertex> chemin = new List<Vertex>();
            List<Vertex> Sommets_a_ouvrir = new List<Vertex>();
            Vertex Sommet_ouvert;
            //on initialise les couts à l'infini pour tous les Sommets 
            foreach (Vertex sta in les_stations)
            {
                sta.set_cout(double.MaxValue);
                sta.set_pred(null);
                Sommets_a_ouvrir.Add(sta);
            }
            depart.set_cout(0);//evidemment
            Sommet_ouvert = ouvre_min(Sommets_a_ouvrir);
            //on verifie qu'il existe au moins un arc liant le Sommet ouvert aux Sommets restants et que l'on n'est pas à l'arrivee


            while (Sommet_ouvert != destination)
            {



                foreach (Vertex s in Sommets_a_ouvrir)
                {
                    double val = Sommet_ouvert.cout() + Sommet_ouvert.cout_arc(s);
                    if (s.cout() > val)
                    {
                        s.set_cout(val);
                        s.set_pred(Sommet_ouvert);
                    }
                }
                Sommet_ouvert = ouvre_min(Sommets_a_ouvrir);

            }
            Sommets_a_ouvrir.Clear();
            if (destination.cout() == double.MaxValue)
            {
                //le graphe est pas connexe il nya pas de chemin possible
                Console.WriteLine("Il nya pas de chemin possible entre " + depart.nom + "  et " + destination.nom);
            }
            else
            //construction du chemin
            {
                while (Sommet_ouvert != depart)
                {
                    chemin.Add(Sommet_ouvert);
                    Sommet_ouvert = Sommet_ouvert.get_pred();
                }


            }
            chemin.Add(depart);
            chemin.Reverse();
            return chemin;
        }

        public Vertex trouver_Sommet(string nom)
        {
            foreach (Vertex s in les_stations)
                if (s.nom == nom)
                    return s;
            return null;

        }
    }
}